package code.oldCode.classic150;

import utils.ListNode;

import java.util.*;

/**
 * @author cuihaoran
 * @date 2024/12/17
 */
public class Classic150_linkedList {

    /* 141. 环形链表 */
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head))
                return true;
            set.add(head);
            head = head.next;
        }
        return false;
    }

    /* 2. 两数相加 */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0, null);
        ListNode pos = root;
        int add = 0;
        while (l1 != null && l2 != null) {
            int num = (l1.val + l2.val + add) % 10;
            add = (l1.val + l2.val + add) / 10;
            ListNode newNode = new ListNode(num, null);
            pos.next = newNode;
            pos = pos.next;

            l1 = l1.next;
            l2 = l2.next;
        }
        while (l1 != null) {
            int num = (l1.val + add) % 10;
            add = (l1.val + +add) / 10;
            ListNode newNode = new ListNode(num, null);
            pos.next = newNode;
            pos = pos.next;

            l1 = l1.next;
        }
        while (l2 != null) {
            int num = (l2.val + add) % 10;
            add = (l2.val + +add) / 10;
            ListNode newNode = new ListNode(num, null);
            pos.next = newNode;
            pos = pos.next;

            l2 = l2.next;
        }
        if (add != 0) {
            ListNode newNode = new ListNode(add, null);
            pos.next = newNode;
        }
        return root.next;
    }

    /* 21. 合并两个有序链表 */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode root = new ListNode(0, null);
        ListNode pos = root;
        ListNode addNode;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                addNode = new ListNode(list1.val, null);
                list1 = list1.next;
            } else {
                addNode = new ListNode(list2.val, null);
                list2 = list2.next;
            }
            pos.next = addNode;
            pos = pos.next;
        }
        while (list1 != null) {
            addNode = new ListNode(list1.val, null);
            list1 = list1.next;
            pos.next = addNode;
            pos = pos.next;
        }
        while (list2 != null) {
            addNode = new ListNode(list2.val, null);
            list2 = list2.next;
            pos.next = addNode;
            pos = pos.next;
        }
        return root.next;
    }

    /* 138. 随机链表的复制 */
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        Node newHead = new Node(0);
        Node oldPos = head;
        Node newPos = newHead;
        Map<Node, Node> map = new HashMap<>();
        while (oldPos != null) {
            // 新节点不在map
            if (!map.containsKey(oldPos)) {
                newPos.next = new Node(oldPos.val);
                map.put(oldPos, newPos.next);
            }
            // 新节点在map
            else {
                newPos.next = map.get(oldPos);
            }
            newPos = newPos.next;
            // 赋值当前随机节点
            if (oldPos.random != null) {
                if (!map.containsKey(oldPos.random)) {
                    Node newRandom = new Node(oldPos.random.val);
                    map.put(oldPos.random, newRandom);
                }
                newPos.random = map.get(oldPos.random);
            }
            oldPos = oldPos.next;
        }

        return newHead.next;
    }

    /* 92. 反转链表 II */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 这个方法很简单，用到一个栈，但是修改节点值了，一般的规则是不允许修改值的
        Deque<Integer> deque = new ArrayDeque<>();
        int pos = 1;
        ListNode p = head;
        while (pos <= right) {
            if (pos >= left)
                deque.push(p.val);
            p = p.next;
            pos++;
        }
        pos = 1;
        p = head;
        while (pos <= right) {
            if (pos >= left)
                p.val = deque.pop();
            p = p.next;
            pos++;
        }
        return head;
    }

    public ListNode reverseBetween_noValueChanged(ListNode head, int left, int right) {
        // 只修改节点连接，不修改值，但感觉思路类似 [3 -> 5], 1, 2
        Deque<ListNode> deque = new ArrayDeque<>();
        int pos = 1;
        ListNode p = head;
        ListNode leftOne = null;
        ListNode rightOne;
        while (pos <= right) {
            if (pos >= left)
                deque.push(p);
            if (pos == left - 1)
                leftOne = p;
            p = p.next;
            pos++;
        }
        rightOne = p;
        // 区间左面连接最右
        if (leftOne != null) {
            leftOne.next = deque.peek();
        } else {
            // 如果区间包括第一个，那么head需要换
            head = deque.peek();
        }
        // 区间右面连接最左
        if (deque.peekLast() != null) {
            deque.peekLast().next = rightOne;
        }
        // deque内部反转
        ListNode reNode = deque.pop();
        while (!deque.isEmpty()) {
            ListNode tempNode = deque.pop();
            reNode.next = tempNode;
            reNode = tempNode;
        }
        return head;
    }

    public ListNode reverseBetween_noValueChanged_noDeque(ListNode head, int left, int right) {
        // 其实deque都用不上，直接遍历一遍就能反转，就不用O(n)的时间复杂度了
        int pos = 1;
        ListNode p = head;
        ListNode leftOne = null;        // 区间左面第一个
        ListNode rightOne = null;              // 区间右面第一个
        ListNode leftNode = null;       // 区间最左面的
        ListNode rightNode = null;      // 区间最右面的
        ListNode pre = null;            // 反转部分遍历到的上一个
        while (p != null) {
            // 反转部分
            if (pos >= left && pos <= right) {
                // 特殊位置变量赋值
                if (pos == left)
                    leftNode = p;
                if (pos == right)
                    rightNode = p;
                // 第一个反转部分的，设为pre
                if (pos == left) {
                    pre = p;
                    p = p.next;
                }
                // 第二个反转开始
                else {
                    ListNode temp = p.next;
                    p.next = pre;
                    pre = p;
                    p = temp;
                }
            }
            // 不反转部分
            else {
                if (pos == left - 1)
                    leftOne = p;
                else if (pos == right + 1)
                    rightOne = p;
                p = p.next;
            }
            pos++;
        }
        // 区间左面连接最右
        if (leftOne != null) {
            leftOne.next = rightNode;
        } else {
            // 如果区间包括第一个，那么head需要换
            head = rightNode;
        }
        // 区间右面连接最左
        if (leftNode != null) {
            leftNode.next = rightOne;
        }

        return head;
    }

    /* 25. K 个一组翻转链表 */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode lastGroupHead = null;
        ListNode nextGroupHead = null;
        ListNode first = null;
        ListNode last = null;
        ListNode preNode = null;
        int countNow = 0;
        ListNode pos = head;
        while (pos != null) {
            countNow++;
            ListNode tempNext = pos.next;
            if (countNow == 1) {
                lastGroupHead = preNode;
                first = pos;
            }
            if (countNow == k) {
                nextGroupHead = tempNext;
                last = pos;
                // 处理反转，必须到k处理
                ListNode tempPos = first;
                ListNode tempPre = null;
                for (int i = 0; i < k; i++) {
                    ListNode tempNext2 = tempPos.next;
                    if (tempPre != null) {
                        tempPos.next = tempPre;
                    }
                    tempPre = tempPos;
                    tempPos = tempNext2;
                }
                // 处理首尾，必须到k处理
                first.next = nextGroupHead;
                if (lastGroupHead != null)
                    lastGroupHead.next = last;
                else if (first == head)
                    head = last;
            }
            // 为下一轮赋值
            preNode = countNow == k ? first : pos;
            countNow = countNow == k ? 0 : countNow;
            pos = tempNext;
        }
        return head;
    }

    /* 19. 删除链表的倒数第 N 个结点 */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode right = head;
        ListNode left = head;
        ListNode preLeft = null;
        // 右指针提前走n-1步
        for (int i = 0; i < n - 1; i++) {
            right = right.next;
        }
        while (right != null) {
            // 此时删除left节点
            if (right.next == null) {
                // 要删的在第一个
                if (preLeft == null) {
                    head = left.next;
                }
                // 要删的在最后一个
                else if (left.next == null) {
                    preLeft.next = null;
                }
                // 要删的在中间
                else {
                    preLeft.next = left.next;
                }
            }
            preLeft = left;
            left = left.next;
            right = right.next;
        }
        return head;
    }

    /* 82. 删除排序链表中的重复元素 II */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null)
            return null;
        // 不用map，双指针
        ListNode root = new ListNode(0, head);
        ListNode pos = head;
        ListNode lag = root;
        while (pos.next != null) {
            if (pos.next.val != pos.val) {
                pos = pos.next;
                lag = lag.next;
            } else {
                // pos跳过这个数
                int repeatNum = pos.val;
                while (pos != null && pos.val == repeatNum) {
                    pos = pos.next;
                }
                // 如果是第一个数，则head更新为pos
                if (lag == root)
                    head = pos;
                // lag的下一个更新为pos
                lag.next = pos;
                // 如果遍历完了，则直接返回
                if (pos == null)
                    return head;
            }
        }

        return head;
    }

    /* 61. 旋转链表 */
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null)
            return null;
        ListNode first = head;
        ListNode last = null;
        ListNode kth = head;
        ListNode k_1th = null;
        ListNode p = head;
        // 确定链表的长度
        int len = 0;
        while (p != null) {
            if (p.next == null)
                last = p;
            len++;
            p = p.next;
        }
        // 规范化k
        k = k % len;
        if (k == 0)
            return head;
        // 找到倒数第k个元素，使其变为head，第k-1个元素的next设为null，最后一个元素接上第一个元素
        p = head;
        for (int i = 0; i < k; i++) {
            p = p.next;
        }
        while (p != null) {
            if (k_1th == null)
                k_1th = kth;
            else
                k_1th = k_1th.next;
            p = p.next;
            kth = kth.next;
        }
        head = kth;
        k_1th.next = null;
        last.next = first;

        return head;
    }

    /* 86. 分隔链表 */
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0, null);
        ListNode big = new ListNode(0, null);
        ListNode p = head;
        ListNode smallP = small;
        ListNode bigP = big;
        while (p != null) {
            if (p.val < x) {
                smallP.next = p;
                smallP = smallP.next;
            } else {
                bigP.next = p;
                bigP = bigP.next;
            }
            p = p.next;
        }
        smallP.next = big.next;
        bigP.next = null;

        return small.next;
    }

    /* 146. LRU 缓存 */
    class LRUCache {

        DoubleLinkedList head;
        DoubleLinkedList tail;

        // map，定位链表位置
        Map<Integer, DoubleLinkedList> map;

        // 长度
        int capacity;

        public LRUCache(int capacity) {
            this.head = new DoubleLinkedList();
            this.tail = new DoubleLinkedList();
            head.next = tail;
            head.pre = null;
            tail.next = null;
            tail.pre = head;
            map = new HashMap<>();
            this.capacity = capacity;
        }

        public int get(int key) {
            // 如果没有，-1
            if (!map.containsKey(key))
                return -1;
            // 如果有，放在最前
            else {
                // 删掉原来位置的
                DoubleLinkedList node = map.get(key);
                DoubleLinkedList pre = node.pre;
                DoubleLinkedList next = node.next;
                pre.next = next;
                next.pre = pre;
                // 放在第一个
                DoubleLinkedList tempNext = head.next;
                head.next = node;
                node.pre = head;
                node.next = tempNext;
                tempNext.pre = node;

                return node.val;
            }
        }

        public void put(int key, int value) {
            // 如果不存在
            if (!map.containsKey(key)) {
                // 赋值
                DoubleLinkedList node = new DoubleLinkedList();
                node.val = value;
                node.key = key;
                map.put(key, node);
                // 放在第一个
                DoubleLinkedList tempNext = head.next;
                head.next = node;
                node.pre = head;
                node.next = tempNext;
                tempNext.pre = node;
                // 超长，去掉最后一个
                if (map.size() > capacity) {
                    DoubleLinkedList lastNode = tail.pre;
                    map.remove(lastNode.key);

                    DoubleLinkedList newLastNode = tail.pre.pre;
                    newLastNode.next = tail;
                    tail.pre = newLastNode;
                }
            }
            // 如果已存在，更新，放在第一个
            else {
                DoubleLinkedList node = map.get(key);
                node.val = value;
                map.put(key, node);
                // 删掉原来位置的
                DoubleLinkedList pre = node.pre;
                DoubleLinkedList next = node.next;
                pre.next = next;
                next.pre = pre;
                // 放在第一个
                DoubleLinkedList tempNext = head.next;
                head.next = node;
                node.pre = head;
                node.next = tempNext;
                tempNext.pre = node;
            }
        }
    }

    // 双向链表
    class DoubleLinkedList {
        int key;
        int val;
        DoubleLinkedList pre;
        DoubleLinkedList next;
    }

    public static void main(String[] args) {
        Classic150_linkedList list = new Classic150_linkedList();
    }
}
